//  binary  search  tree  二叉搜索树


class Node {
    constructor(element, parent) {
        this.element = element
        this.parent = parent
        this.left = null
        this.right = null

    }
}


class BST {
    constructor(compare) {
        this.root = null
        this.compare = compare || this.compareFn
    }
    compareFn(currentElement, element) {
        return currentElement > element
    }
    add(element) {
        if (this.root == null) {
            this.root = new Node(element, null)
        } else {
            let curNode = this.root
            //     if (element < this.root.element) {
            //         this.root.left = new Node(element, curNode)
            //     } else {
            //         this.root.right = new Node(element, curNode)
            //     }
            // }
            let parent = null
            let isLeft = false
            while (curNode) {
                parent = curNode
                isLeft = this.compare(curNode.element, element)
                if (isLeft) {
                    curNode = curNode.left
                } else {
                    curNode = curNode.right
                }
            }
            let newNode = new Node(element, parent)
            if (isLeft) {
                parent.left = newNode
            } else {
                parent.right = newNode
            }
        }
    }
    perOrderTraversal(cb) { // 先序遍历
        const next = (node) => {
            if (node == null) return
            cb(node)
            next(node.left)
            next(node.right)
        }
        next(this.root)
    }
    inOrderTraversal(cb) { // 中序遍历
        const next = (node) => {
            if (node == null) return
            next(node.left)
            cb(node)
            next(node.right)
        }
        next(this.root)
    }
    postOrderTraversal(cb) { // 后序遍历
        const next = (node) => {
            if (node == null) return
            next(node.left)
            next(node.right)
            cb(node)

        }
        next(this.root)
    }
    levelOrderTraversal(cb) { // 层序遍历
        let stack = [this.root]
        let currNode
        let i = 0
        while (stack[i]) {
            currNode = stack[i]
            cb(currNode)
            if (currNode.left) {
                stack.push(currNode.left)
            }
            if (currNode.right) {
                stack.push(currNode.right)
            }
            i++
        }
    }

    invertTree() { // 翻转二叉树
        const next = (node) => {
            if (node == null) return
            let r = node.right
            node.right = node.left
            node.left = r
            next(node.left)
            next(node.right)
            return node
        }

        next(this.root)
    }
}

let bst = new BST((a, b) => {
    return a.age > b.age
})
let arr = [{ age: 10 }, { age: 8 }, { age: 6 }, { age: 19 }, { age: 15 }, { age: 22 }]
arr.forEach(v => {
    bst.add(v)
})

    // console.dir(bst, { depth: 20 })

    // 树的遍历方式  广度优先  深度优先   
    /***
     * 先序遍历 perOrderTraversal：   根  左  右   // 按bst顺序
     * 中序遍历 inOrderTraversal：    左  根  右    //  特点 从小到大
     * 层序遍历 levelOrderTraversal：   根 左 右  左左 左右  右左 右右 
     * 后序遍历 postOrderTraversal：   左  右  根    // 特点 先子后父 
     */
    +
    bst.invertTree()
bst.perOrderTraversal(v => { // 按bst顺序
    // console.log(v.element.age) // 10  8 6  19  15 22
})

bst.inOrderTraversal(v => {  // 按小 到大 顺序
    // console.log(v.element.age) // 6 8 10 15 19 22
})
bst.levelOrderTraversal(v => {
    // console.log(v.element.age) // 10  8 19 6 15 22
})
bst.postOrderTraversal(v => {
    console.log(v.element.age) //  6 8 15 22 19 10
})


